// https://www.lintcode.com/problem/interleaving-string/description

class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
     
    // 个 法一：回溯
    // bool help(queue<char> q1, queue<char> q2, string s)
    // {
    //     for (int i = 0; i < s.size(); ++i)
    //     {
    //         if (s[i] == q1.front() || s[i] == q2.front())
    //         {
    //             if (s[i] == q1.front() && s[i] == q2.front())
    //             {
    //                 queue<char> tmp = q1;
    //                 tmp.pop();
    //                 if (help(tmp, q2, s.substr(i + 1, s.length() - i))) return true;
    //                 tmp = q2;
    //                 tmp.pop();
    //                 return help(q1, tmp, s.substr(i + 1, s.length() - i));
    //             }
    //             else if (s[i] == q1.front()) q1.pop();
    //             else q2.pop();
    //         }
    //         else return false;
    //     }
    //     return q1.empty() && q2.empty();
    // }
    // bool isInterleave(string &s1, string &s2, string &s3) {
    //     if (s1.empty()) return s3 == s2;
    //     if (s2.empty()) return s3 == s1;
    //     queue<char> q1;
    //     queue<char> q2;
    //     for (int i = 0; i < s1.size(); ++i) q1.push(s1[i]);
    //     for (int i = 0; i < s2.size(); ++i) q2.push(s2[i]);
    //     return help(q1, q2, s3);
    // }
    
    // 个 法二：dfs
    // bool help(string s1, string s2, string s3, int p1, int p2, int p3)
    // {
    //     while (p3 < s3.length())
    //     {
    //         if (p1 == s1.length()) 
    //             return s2.substr(p2, s2.length() - p2 + 1) ==
    //                 s3.substr(p3, s3.length() - p3 + 1);
    //         if (p2 == s2.length()) 
    //             return s1.substr(p1, s1.length() - p1 + 1) ==
    //                 s3.substr(p3, s3.length() - p3 + 1);
    //         if (s1[p1] == s3[p3] || s2[p2] == s3[p3]) 
    //         {
    //             if (s1[p1] == s3[p3] && s2[p2] == s3[p3]) 
    //             {
    //                 return help(s1, s2, s3, p1 + 1, p2, p3 + 1) || 
    //                 help(s1, s2, s3, p1, p2 + 1, p3 + 1);
    //             }
    //             else if (s1[p1] == s3[p3]) p1++;
    //             else p2++;
    //             p3++;
    //         }
    //         else return false;
    //     }
    //     return p1 == s1.length() && p2 == s2.length();
    // }
    // bool isInterleave(string &s1, string &s2, string &s3) {
    //     return help(s1, s2, s3, 0, 0, 0);
    // }
    
    // 法三：动态规划
    // dp[i][j]代表由s1的前i个字母和s2的前j个字母是否能构成当前i+j个字母。
    // 然后状态转移即可。（看第i+j+1个是否能被s1的第i+1个构成或被s2的第j+1个构成）
    bool isInterleave(string &s1, string &s2, string &s3) {
        int m = s1.size();
        int n = s2.size();
        if (s3.size() != m + n) return false;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= m; ++i)
        {
            if (s3[i - 1] == s1[i - 1]) dp[i][0] = dp[i - 1][0];
        }
        for (int i = 1; i <= n; ++i)
        {
            if (s3[i - 1] == s2[i - 1]) dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                // 不能混在一起写
                // if (s3[i + j - 1] == s1[i - 1] || s3[i + j - 1] == s2[j - 1]) 
                // {
                //     dp[i][j] = (dp[i - 1][j] || dp[i][j - 1]);
                // } 
                if (s3[i + j - 1] == s1[i - 1]) dp[i][j] = dp[i - 1][j];
                // else if (s3[i + j - 1] == s2[j - 1]) dp[i][j] = dp[i][j - 1];
                if (s3[i + j - 1] == s2[j - 1]) dp[i][j] = dp[i][j] || dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};